package com.company;

public class Solution {
    public int findBestValue(int[] arr, int target) {
        if (arr == null) {
            return -1;
        }

        int max = target;
        int min = 0;
        while (max > min) {
            int mid = (max + min) / 2;
            int sum1 = 0;
            int sum2 = 0;
            for (int i = 0; i < arr.length; i++) {
                sum1 += Math.min(arr[i], mid);
                sum2 += Math.min(arr[i], mid + 1);
            }
            if (Math.abs(sum1 - target) <= Math.abs(sum2 - target)) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}
